class Solution {
public:
    int numDecodings(string s) {
        int sz=s.size();
        vector<int> dp(sz);
        if(s[0]!='0')
            dp[0]++;
        else 
            return 0;

        if(sz==1)
            return dp[0];

        if(s[1]!='0') 
            dp[1]+=dp[0];
        if((s[0]-'0')*10+s[1]-'0'<27) 
            dp[1]++;
        if(dp[1] == 0)
            return 0;

        for(int i=2;i<sz;++i)
        {
            if(s[i]!='0')
                dp[i]+=dp[i-1];

            if(((s[i-1]-'0')*10+(s[i]-'0'))<27&&((s[i-1]-'0')*10+(s[i]-'0'))>9)
                dp[i]+=dp[i-2];
            if(!dp[i])
                return 0;
        }
        return dp[sz-1];
    }
};
